HW#1 --- last modified March 02 2019 17:19:23..

Solution set .

Due date: Feb 18

Files to be submitted:
  maze.scm

Purpose: To quickly get familiar with Scheme. To experiment with best first search algorithms.

Specification:

The suggested study problems for this assignment are: 3.8, 3.13, 4.1, 4.7. You do not need to turn these in.

For this assignment you will write a function which determines a path from the start position to the end position of a maze. We define a maze in two steps. First, a floorplan is a square array of 0's and 1's. A 0 indicates an unoccupied square. That is, a square a player can walk in. A 1 indicates a sqaure a player cannot occupy (can think of as a wall). A path from square s in a floorplan to square t is a sequence of left, right, up, down moves from square s such that at each step in the sequence the move is onto an unoccupied square in the floorplan. A floorplan is a maze if the top left square is unoccupied (this is the start position) and the bottom right square is unoccupied (this is the end position) and there is a path between these two squares.

A maze-game is a Scheme object that supports the following messages:

'init!  -- initialize the maze with the player in the start square.

'copy  -- returns another object which is a copy of the current board.

'up! -- move the player up one square. If succeed return true else false.
'down! -- move the player down one square. If succeed return true else false
'left! -- move the player left one square. If succeed return true else false.
'right! -- move the player right one square. If succeed return true else false.

'size -- returns the size of the dimension of the maze. (i.e., n if it is
an n x n-maze).

'distance-up -- returns the number of unoccupied square in the upward
direction from the current location until one hits the edge of the maze
or an occupied square.

The next three messages are similar but for the corresponding direction:

'distance-down
'distance-right
'distance-left

'goal? -- returns #t if player is at the end of maze.

For this assignment your job is to write a program find-path-maze-game which on input a maze-game outputs a list containing a sequence of 'up!, 'down!, 'left!, 'right! messages which when applied in order yield a path from the start position to the end position in the maze-game. The goal further is to get your program to do this better than anybody else's in the class.

As an example of how your program may be tested. Suppose the constructor make-random-maze-game creates a maze of the supplied size. So to create a maze at the Scheme prompt one could do:

>(define maze1 (make-random-maze-game 5))
>;we could test out this maze...
>(maze1 'init!) ;initialize to start location
>(maze1 'down!) ;try to move the player down one position in the maze
#t ; if we got this back then move succeeded
> ; let's try to solve maze with your code
>(find-path-maze-game maze1)
('right! 'right! 'right! 'right! 'down! 'down! 'down! 'down!)
                                                      ;suppose got this
                                                      ; as the answer then
>(maze1 'init!)
>(maze1 'right!)
>(maze1 'right!)
>(maze1 'right!)
>(maze1 'right!)
>(maze1 'down!)
>(maze1 'down!)
>(maze1 'down!)
>(maze1 'down!)
>(maze1 'goal?)
#t                                                    ; should return true
> ; the following is an example of how distance-right works
>(maze1 'init!)
>(maze1 'distance-right)
4

As one more example of a possible maze-game, here is an example implementation of a constructor that can be used to create a blank maze of size n:

;;;
;;; function to create a blank maze game of size n
;;;
(define make-blank-game
  (lambda (n)
    (let ((size n)          ;size of board
          (edge (- n 1))    ;last column or row in board
          (player-x 0)      ;default player horizontal position
          (player-y 0))     ;default player vertical position

      (lambda (msg . args)
        (cond

          ((eqv? msg 'init!)
           ;;put player in default position
           (begin
             (set! player-x 0)
             (set! player-y 0)))

          ((eqv? msg 'size)
           ;;return size of maze-game
           size)

          ((eqv? msg 'goal?)
           (if (and (= player-x edge) (= player-y edge)) #t #f))

          ((eqv? msg 'left!)
           ;;check if its legal to move left
           ;; if so, do it
           (if (> player-x 0)
               (begin
                 (set! player-x (- player-x 1))
                 #t)
               #f))

          ((eqv? msg 'up!)
           ;;check if its legal to move up
           ;; if so, do it
           (if (> player-y 0)
               (begin
                 (set! player-y (- player-y 1))
                 #t)
               #f))

          ((eqv? msg 'right!)
           ;;check if its legal to move right
           ;; if so, do it
           (if (< player-x edge)
               (begin
                 (set! player-x (+ player-x 1))
                 #t)
               #f))

          ((eqv? msg 'down!)
           ;;check if its legal to move down
           ;; if so, do it
           (if (< player-y edge)
               (begin
                 (set! player-y (+ player-y 1))
                 #t)
               #f))

          ((eqv? msg 'distance-left)
           ;;return numbers of visible squares to left
           player-x)

          ((eqv? msg 'distance-right)
           ;;return numbers of visible squares to right
           (- edge player-x))

           ((eqv? msg 'distance-up)
            ;;return numbers of visible squares to up
            player-y)

          ((eqv? msg 'distance-down)
           ;;return numbers of visible squares to down
           (- edge player-y))

          (else "bad method"))))))

To use the above could have a line like:

(define maze2 (make-blank-game 10))

This is a link to some code discussed in class for creating large boards and for doing greedy search.

Point Breakdown